package 回溯;

import java.time.Instant;
import java.util.*;

/**
 * todo
 *
 * @author songZiHao
 * @version 1.0.0
 * @ClassName 全排列46.java
 * @createTime 2022年10月28日 17:09:00
 */
public class 全排列46 {
	List<List<Integer>> result = new ArrayList<>();
	LinkedList<Integer> tempList = new LinkedList<>();

	public List<List<Integer>> permute(int[] nums) {
		//用一个数组来表示使用过的数字
		backTrace(nums, 0, new boolean[nums.length]);
		return result;
	}

	public void backTrace(int[] nums, int size, boolean[] used) {
		//结束条件
		if (size == nums.length) {
			result.add(new ArrayList<>(tempList));
			return;
		}
		//循环
		for (int i = 0; i < nums.length; i++) {
			//做选择:如果已经用了就不能用了
			if (used[i]) {
				continue;
			}
			tempList.add(nums[i]);
			used[i] = true;
			//继续回溯
			backTrace(nums, tempList.size(), used);
			//取消选择
			tempList.removeLast();
			used[i] = false;
		}
	}

	public static void main(String[] args) {
		System.out.println(Integer.valueOf("101",2));
	}

}
